#include <stdio.h>
#include "genlib.h"
#include "simpio.h"

#define MAX_COLORS 10

static bool IsMeasurable(int target, int weights[], int nWeights);
static int getWeight(void);

int main() {
	int i = 0, weights[MAX_COLORS], weight, nWeights=0, sumWeights=0;
	
	printf("-- Assignment 2 --\n\n");
	printf("Enter weights. Max 10 number of weights. End with -1.\n\n");

	// Get input from user:
	while (nWeights < MAX_COLORS) {
		printf("Weight: ");
		weight = getWeight();
		if (weight == -1) {
			if (nWeights > 0 ) break;
			else printf("Add at least one weight.\n");
		} else {
			weights[i] = weight;
			sumWeights += weights[i];
			nWeights++;		
			i++;
		}
	}

	printf("\n");

	// Loop trough the sum of weights and see if "i" is measurable:
	for (i=1; i<=sumWeights; i++)
		printf("%3d is %smeasurable.\n", i,
			IsMeasurable(i, weights, nWeights) ? "" : "NOT ");

	printf("\n");
	system("pause");
}

static int getWeight() {
	int weight;
	while ( TRUE ) {
		weight = GetInteger();
		return weight > 0 ? weight : -1;
	}
}

static bool IsMeasurable(int target, int weights[], int nWeights) {
	int i, wSum = 0;
	
	// Sum the weights:
	for (i=0; i<nWeights; i++)
		wSum += weights[i];
	
	if (target == wSum) return TRUE;
	else if (!nWeights) return FALSE;
	
	return IsMeasurable(target+weights[0], weights+1, nWeights-1)
		|| IsMeasurable(target-weights[0], weights+1, nWeights-1)
		|| IsMeasurable(target, weights+1, nWeights-1);
}